//题目:
// 一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。
// 这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
// 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
// 给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
//代码
class Solution 
{
public:
    int rob(vector<int>& nums) 
    {
        if(nums.size()==1) return nums[0];
        if(nums.size()==2) return max(nums[0],nums[1]);
        if(nums.size()==3) return max({nums[0],nums[1],nums[2]});
        
        int n=nums.size();
        //1.创建dp表
        vector<int> f(n);//偷第1个位置时，从初始位置到第i个位置的最大金额
        vector<int> g(n);//不偷第1个位置时，从初始位置到第i个位置的最大金额
        //2.初始化
        f[0]=nums[0],f[1]=f[0];f[2]=nums[2]+f[0];
        g[0]=0,g[1]=nums[1],g[2]=nums[2]+g[0];
        //3.填表————动态转移方程:dp[i]=nums[i]+max(dp[i-2],dp[i-3]);
        for(int i=3;i<n;i++)
        {
            if(i==n-1)//处理边界情况
                f[i]=max(f[i-2],f[i-3]);//f表示偷第一个房间，所以最后一个nums[i]不能偷
            else
                f[i]=nums[i]+max(f[i-2],f[i-3]);
            
            g[i]=nums[i]+max(g[i-2],g[i-3]);//g表示不偷第一个房间，所以最后一个nums[i]能偷
        }
        return max({f[n-2],f[n-1],g[n-2],g[n-1]});
    }
};